package com.origin.niuke.tree;

import general_class.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 二叉树的最大宽度
 * 算法：深度优先搜索
 * 给每个节点标号, 节点为 1, 则左节点为 2 ^ 1, 右节点为 2 ^ 1 + 1
 *
 * @author yezh
 * @date 2023/2/21 7:18
 */
public class NC204 {

    Map<Integer, Integer> map;
    int ans = 0;
    public int widthOfBinaryTree(TreeNode root) {
        // write code here
        map = new HashMap<>();
        dfs(1, 1, root);
        return ans;
    }

    void dfs(int u, int depth, TreeNode node) {
        if (node == null) return;
        if (!map.containsKey(depth)) map.put(depth, u);
        // 防止溢出
        u = u - map.get(depth) + 1;
        if (u > ans) ans = u;
        dfs(u << 1, depth + 1, node.left);
        dfs(u << 1 | 1, depth + 1, node.right);
    }

}
